package com.demo78_子集;

import java.util.*;

/**
 * 这个题是获取一个数组里面的所有的子集
 *
 * 这里的整体思想是:  借助于之前的组合问题,  每次得到的是这个大小为 k 的所有的组合,  然后k 从 0 - 数组元素的大小
 *
 * 就得到了所有的子集 ~   但是好像还是不太方便~
 *
 *
 */
public class Solution {
    public static int time;

    public static void main(String[] args) {
        int[] ints = {1,2,3,4,5,6,7,8,9,10};
        List<List<Integer>> subsets = subsets(ints);
        System.out.println(time);
    }
    public static List<List<Integer>> subsets(int[] nums) {


        List list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> empty = new ArrayList<>();
        list.add(empty);
        if (nums.length==0){
            return list;
        }
        for (int i = 1; i <= nums.length; i++) {
            List result = getResult(nums, i);
            for (Object o : result) {
                list.add(o);
            }
        }


        return list;
    }

    public static List getResult(int[] nums,int k){
        ArrayList<Integer> path = new ArrayList<>();
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (k==0){
            return arrayLists;
        }
        // 开始的索引,  需要收集的集合的大小, 数组, 路径集合, 结果集合
        dfs(0,k,nums,path,arrayLists);

        // 返回结果
        return arrayLists;
    }

    private static void dfs(int  startIndex, int k, int[] nums, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> arrayLists) {
        // 边界条件
        if (path.size()==k){
            // 如果集合的个数  == k
            ArrayList<Integer> list = new ArrayList<>();
            for (Integer item : path) {
                list.add(item);
            }
            // 添加到结果集中
            arrayLists.add(list);
            // 返回
            return;
        }

        // 递归
        for (int i = startIndex; i < nums.length; i++) {
            // 剪枝操作
            if (path.size()+(nums.length-i+1)<k){
                return;
            }
            time++;  // 当数组没有这个剪枝操作的时候, 随着这个数组的个数的增加, 这个递归的次数是直接 指数级增加.  当大小为10 , 没有剪枝是6k多次, 剪枝是3k
            // 处理当前元素
            path.add(nums[i]);
            // 递归
            dfs(i+1,k,nums,path,arrayLists);
            // 回溯
            path.remove(path.size()-1);
        }
    }
}
